package algo.sort;

public class ThreeWayQuickSort<T extends Comparable<? super T>> extends QuickSort<T>{

    @Override
    protected void toSort(T[] nums, int left, int right) {
        if (right <= left) return;

        int lessThan = left, index = left + 1, greaterThan = right;
        T value = nums[left];

        while (index <= greaterThan) {
            int cmp = nums[index].compareTo(value);

            if (cmp < 0) {
                swap(nums, lessThan++, index++);
            } else if (cmp > 0) {
                swap(nums, index, greaterThan--);
            } else {
                ++index;
            }
        }
        toSort(nums, left, lessThan - 1);
        toSort(nums, greaterThan + 1, right);
    }

    @Override
    protected void toSortDesc(T[] nums, int left, int right) {
        if (right <= left) return;

        int lessThan = right, index = left + 1, greaterThan = left;
        T value = nums[left];

        while (index <= lessThan) {
            int cmp = nums[index].compareTo(value);

            if (cmp < 0) {
                swap(nums, index, lessThan--);
            } else if (cmp > 0) {
                swap(nums, greaterThan++, index++);
            } else {
                ++index;
            }
        }
        toSortDesc(nums, left, greaterThan - 1);
        toSortDesc(nums, lessThan + 1, right);
    }
}
